﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0081_ShortestPathBinaryMatrix : IAlgorithm
    {
        // 1091. 二进制矩阵中的最短路径

        // 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

        // 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
        //   路径途经的所有单元格都的值都是 0 。
        //   路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

        // 畅通路径的长度 是该路径途经的单元格总数。

        // 提示：
        //  n == grid.length
        //  n == grid[i].length
        //  1 <= n <= 100
        //  grid[i][j] 为 0 或 1

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(ShortestPathBinaryMatrix(grid));
        }
        public int ShortestPathBinaryMatrix(int[][] grid)
        {
            if (grid[0][0] == 1) return -1;
            int ans = 0, n = grid.Length;
            // 8 directions
            int[][] directions = new int[][] { new int[] { -1, 0 }, new int[] { -1, 1 }, new int[] { 0, 1 }, new int[] { 1, 1 }, new int[] { 1, 0 }, new int[] { 1, -1 }, new int[] { 0, -1 }, new int[] { -1, -1 } };
            // Store the current index
            Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(new int[] { 0, 0 });
            bool[,] visited = new bool[n, n];
            visited[0, 0] = true;
            while (queue.Count != 0)
            {
                ans++;
                int length = queue.Count;
                // Traverse through this layer
                for (int i = 0; i < length; ++i)
                {
                    int[] curr = queue.Dequeue();
                    if (curr[0] == n - 1 && curr[1] == n - 1) 
                        return ans;
                    foreach (int[] direction in directions)
                    {
                        int nextX = curr[0] + direction[0], nextY = curr[1] + direction[1];
                        if ((nextX >= 0 && nextX < n) && (nextY >= 0 && nextY < n) && grid[nextX][nextY] == 0 && !visited[nextX, nextY])
                        {
                            visited[nextX, nextY] = true;
                            queue.Enqueue(new int[] { nextX, nextY });
                        }
                    }
                }
            }
            return -1;
        }
    }
}
